package ai.zixing.mashibing.basic_class.class11;

/**
 * 给定两个长度都为N的数组weights和values，
 * weights[i]和values[i]分别代表 i号物品的重量和价值。
 * 给定一个正数bag，表示一个载重bag的袋子，
 * 你装的物品不能超过这个重量。
 * 返回你能装下最多的价值是多少?
 */
public class Code07_Knapsack {

    public static int getMaxValue(int[] w, int[] v, int bag) {
        return process(w, v, 0, 0, bag);
    }

    // index 的货物要还是不要
    // alreadyW 之前的选择，货物的重量达到了多少
    // bag 总载重，w[],v[] 这三个两不变
    // 返回 -1 代表没有方案
    // 返回正数，返回真实的价值
    public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
        if (alreadyW > bag) {
            return -1;
        }
        // 所有货物都选择，还可以放
        if (index == w.length) {
            return 0;
        }
        // 没有要 index 的获取，（alreadyW 没有变，说明没有要货物）
        int p1 = process(w, v, index + 1, alreadyW, bag);
        // 要了当前的货物,需要将当前货物的价值累加
        int p2next = process(w, v, index + 1, alreadyW + w[index], bag);
        int p2 = -1;
        if (p2next != -1) {
            p2 = v[index] + p2next;
        }
        return Math.max(p1, p2);
    }

    // 方案二 ： 背包剩余的空间
    public static int maxValue(int[] w, int[] v, int bag) {
        return process(w, v, 0, bag);
    }

    // index... 货物自由选择
    // 背包还剩余 rest 的空间
    public static int process(int[] w, int[] v, int index, int rest) {
        // 没有剩余空间，返回
        if (rest <= 0) {
            return -1;
        }
        // 没有货物了
        if (index == w.length) {
            return 0;
        }
        // 没有选择当前货物
        int p1 = process(w, v, index + 1, rest);
        // 要了当前的货物
        int p2Next = process(w, v, index + 1, rest - w[index]);
        int p2 = -1;
        if (p2Next != -1) {
            p2 = v[index] + p2Next;
        }
        return Math.max(p1, p2);
    }
}
